/*
 * selectMinNumWithAtLeastSum.cpp
 *
 *  Created on: Sep 12, 2012
 *      Author: jeffrey
 */
#include<iostream>
#include<stdlib.h>
using namespace std;
class SelectMinNumWithAtLeastSum {
public:
	static int select(int array[], int len, int sum) {
		int s = 0, e = len - 1;
		while (s <= e) {
			int p = rand() % (e - s + 1) + s;
			int pos = partition(array, s, e, p);
			int partSum = 0;
			for (int i = e; i >= pos; i--)
				partSum += array[i];
			if (sum > partSum) {
				if (array[pos] >= 0) {
					if (pos > s) {
						sum -= partSum;
						e = pos - 1;
					} else
						return -1;
				} else {
					if (pos < e) {
						s = pos + 1;
					} else
						return -1;
				}

			} else {
				// make sure advancing p still make tmpSum>=sum
				if (pos < e && partSum - array[pos] >= sum) {
					s = pos + 1;
				} else
					// can not advance pps, so pos is the cut point
					return len - pos;
			}

		}
	}
private:
	static int partition(int array[], int s, int e, int p) {
		int pValue = array[p];
		swap(array, p, e);
		int tmp = s;
		for (int i = s; i < e; i++)
			if (array[i] < pValue)
				swap(array, tmp++, i);
		swap(array, tmp, e);
		return tmp;
	}
	static void swap(int array[], int i, int j) {
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}
};
//int main() {
//	for (int i = -13; i < 22; i++) {
//		int a[] = { 1, 3, 2, -8, -6, -100 };
//		cout << i << " " << SelectMinNumWithAtLeastSum::select(a, 6, i) << endl;
//
//	}
//}

